#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
int t,n,m;
const int N=105;
int mp[N][N];
int a[N];
//dp[i][j]表示i位置放j音符的最大值
int dp[N][N];
int main(void){
    scanf("%d",&t);
    while(t--){
        scanf("%d%d",&n,&m);
        for(int i=1;i<=m;i++){
            for(int j=1;j<=m;j++){
                scanf("%d",&mp[i][j]);
            }
        }
        for(int i=1;i<=n;i++){
            scanf("%d",&a[i]);
        }
        memset(dp,0,sizeof(dp));
        //从第二个音符开始，因为第一个音符没有上一个音符
        for(int i=2;i<=n;i++){
            //第一种状态转移，前后两个音符都确定
            if(a[i]>0 && a[i-1]>0){
                dp[i][a[i]]=dp[i-1][a[i-1]]+mp[a[i-1]][a[i]];
            }
            //第二种状态转移，已知当前音符，不知上一个音符，枚举上一个音符
            else if(a[i]>0 && a[i-1]<0){
                for(int k=1;k<=m;k++){
                    dp[i][a[i]]=max(dp[i][a[i]],dp[i-1][k]+mp[k][a[i]]);
                }
            }
            //第三种状态转移，已知上一个音符，不知当前音符，枚举当前音符
            else if(a[i]<0 && a[i-1]>0){
                for(int k=1;k<=m;k++){
                    dp[i][k]=max(dp[i][a[i]],dp[i-1][a[i-1]]+mp[a[i-1]][k]);
                }
            }
            //第四种状态转移，上一个音符和当前音符都不知
            else if(a[i]<0 && a[i-1]<0){
                for(int j=1;j<=m;j++){
                    for(int k=1;k<=m;k++){
                        dp[i][j]=max(dp[i][j],dp[i-1][k]+mp[k][j]);
                    }
                }
            }
        }
        int ans=0;
        for(int i=1;i<=m;i++){
            ans=max(ans,dp[n][i]);
        }
        printf("%d\n",ans);
    }
    return 0;
}